CPSC 545/445 (Autumn 2003) - Class 20: Computational processes in the cell Module 7, Part 1 -- 7.1 membrane computing / P-Systems (Paun, 2000; Paun & Rozenberg, 2001): motivation: biological membranes... - define compartments and relate compartments to their environment - are separators and filters: support active and passive transport of molecules biological model of membrane structure: fluid-mosaic model [Singer & Nicolson; 1972] - membrane = phospolipid bilayer in which protein molecules are totally or partially embedded - phospholipid molecules have polar head (phospate+nitrogen group) and non-polar tail (two fatty acid chains), connected by glycerol -> hydrophilic heads, hydrophobic tails; - phospholipid molecules can move on membrane surface - polarisation of membrane (pos charge on outside, neg on inside) facilitates exit of negative ions, entry of positive ions - membrane is partially permeable: small, non-chared molecules cross almost freely; large molecules pass only when assisted; charged ions pass selectively - passive transfer: diffusion (along concentration gradient) - active transfer: protein channels (pores); some can select molecules for size, others interact with specific proteins (carrier proteins) - other membrane protein functions: catalytic: certain reactions can only take place in presence of certain membrane proteins recognition and binding sites inter-cellular communication (channels across membranes of neighbouring cells) "biological membranes provide a protected and well-equipped space" (natural reaction tube) idea: use basic features of biological membranes as basis of computing model -> p systems simple example: (see separate sheet) -- basic p-systems basic approach & concepts: - hierarchically nested membranes - strings represent multisets - rules local to membranes - principle of nondeterminism and maximal parallelism - rules are "inherited" from mother membranes - rules can export / import results into mother / daughter membranes - output = export from outermost membrane (=skin) formal definition: P system Pi = (V,T,mu, w1,...wm, R1, ...,Rm) V: alphabet of objects T subseteq V: output alphabet C subseteq V-T: catalysts mu: membrane structure, m membranes labeled {1,...,m}; m = degree of Pi w_i, 1<=i<=m: strings representing multisets over V associated with membranes 1...m R_i, 1<=i<=m: sets of evolution rules associated with regions 1..m evolution rules u->v: u string oever V v = v' (or v=v'delta for dissolving membrane) v': string over {a_here, a_out, a_in_j | a \in V, 1<=j<=m} length of u = radius of u->v (a_here often notated a) semantics: configuration = (m+1)-tuple (mu, w1,...,wm) transformation (config -> config): applying rules of each region in nondet and max par manner (note: a region is the space inside a membrane, but outside its daughter membranes; rules are not inherited from mother membranes) transformation = 1 macro-step consists of micro-steps: - assign occurrences of objects from region r to rules of r (choose objects and rules non-det until no further assignment possible) - remove all assigned objects from w_r; add all objects from rhs of chosen rules with "transfer commands" - execute transfers (out and in_j) by moving objects between regions and removing transfer commands computation halts when no rule is applicable in any region result of halting computation = number of objects sent through outmost membrane (skin) to environment during computation (non-halting computations have no output) types of p-systems: - cooperative systems: contains rules with radius > 1 - catalytic systems: only rules with radius > 1 are of form ca->cv (c \in C, a \in V-C, v \in (V-C)^\ast and no other rules contain catalysts - purely communicative P-systems (objects only moved, not changed; use carriers) simple extensions: - priorities of rules (partial order in each region) - dissolving membranes (special u->v\delta rules); objects remain in surrounding membrane, rules are removed, skin cannot be dissolved - blocking/unblocking membranes (special u->\delta, u ->\tau rules make enclosing membrane impermeable/permeable) -- questions: - computational power / competence? - computational complexity? - modelling adequateness? results: - universality of P-systems: P systems have same computational power as turing machines more precisely: basic P system with 1 memabrane, bistable catalysts (ca->c'u, c'a->c'u), no prior, no membrane dissolution/blocking generate Parikh sets of RE languages (same for 2 membranes, with priorities; or: 4 membranes, perm control + dissol, no prior) proof based on result that matrix grammars with appearance checking generate the RE languages - standard P-systems can be sim by det TM with poly slowdown - P-systems with active membranes (charged, division) can solve SAT in lin time, HPP in quadr time (need exponential number of objects = space; proof based on generate & check alg for hpp, similar to alg used in dna computing, e.g., adleman) - similar result for P-systems with string replication -- various extensions (paun et al): - use charged membranes / object for selective transport - increase/decrease permeability (thickness) of membranes - use strings (instead of symbols) as objects; P systems with rewriting P systems with splicing - use multisets of strings recombinatotion, crossover - membrane division dividing replicates contents, only divide elementary membranes ("leaves") or arbitrary - replication of strings - creating membranes - merge membranes [head; 2001] - other membrane operations: divide, create, separate; move through (with content) - rules with energy accounting - use arbitrary graphs instead of tree structure of membrane nbh ... implementations of some variants available from http://psystems.disco.unimib.it/ related formalisms: - H systems [see Head, 1987; Paun et al, 1998] - Gamma language [Banatre, Coutant, Le Metayer, 1988] - Chemical Abstract Machine [Berry, Boudol, 1992] - L Systems --- resources: p-systems: http://dna.bio.disco.unimib.it/psystems/ -> P Systems Web Page Gheorghe Paun and Grzegorz Rozenberg: A Guide to Membrane Computing; Theoretical Computer Science, to appear. [p0-Mains.zip] -> http://dna.bio.disco.unimib.it/psystems/download/Mains.zip